package leetcode.binaryTree;

import datastructure.tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Description: https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树。
 * <p>
 * 草稿(旧)：2
 * @Author Ammar
 * @Create 2023/3/30 01:15
 */
public class _106_从中序与后序遍历序列构造二叉树 {

    // 后序遍历数组
    static int[] postorder_s;
    // 中序遍历数组值:索引的 hash 表，方便递归子树的时候找出中序遍历中子树的数组的位置
    static Map<Integer, Integer> inorderMap = new HashMap<>();

    public static void main(String[] args) {
        int[] inorder = {4, 2, 8, 5, 9, 1, 6, 10, 3, 7};
        int[] postorder = {4, 8, 9, 5, 2, 10, 6, 7, 3, 1};
        TreeNode treeNode = buildTree(inorder, postorder);
    }

    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        // 将中序遍历数组的每个元素建立索引
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        postorder_s = postorder;
        return buildTree(0, inorder.length - 1, 0, postorder.length - 1);
    }

    /**
     * 中：4 2 8 5 9 1 6 10 3 7
     * 后：4 8 9 5 2 10 6 7 3 1
     *
     * @param is 中序遍历数组中子树的起始 index
     * @param ie 中序遍历数组中子树的截止 index
     * @param ps 后序遍历数组中子树的起始 index
     * @param pe 后序遍历数组中子树的截止 index
     * @return
     */
    public static TreeNode buildTree(int is, int ie, int ps, int pe) {
        if (ie < is || pe < ps) return null;
        int inorderStart;
        int inorderEnd;
        int nodeCount;
        int postorderStart;
        int postorderEnd;
        // 获取根节点
        int root = postorder_s[pe];
        // 构造根节点
        TreeNode<Integer> rootNode = new TreeNode(root, null);
        // 获取中序遍历中根节点的索引 也是左子树节点个数
        int rootIndex = inorderMap.get(root);
        inorderStart = is;
        inorderEnd = rootIndex - 1;
        nodeCount = inorderEnd - inorderStart + 1;
        postorderStart = ps;
        postorderEnd = ps + nodeCount - 1;
        rootNode.left = buildTree(inorderStart, inorderEnd, postorderStart, postorderEnd);
        inorderStart = rootIndex + 1;
        inorderEnd = ie;
        nodeCount = inorderEnd - rootIndex;
        postorderEnd = pe - 1;
        postorderStart = postorderEnd - nodeCount + 1;
        rootNode.right = buildTree(inorderStart, inorderEnd, postorderStart, postorderEnd);
        return rootNode;
    }
}
